package main

import (
	"fmt"
	"sort"
)

//#link: https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
func main() {
	s := "abc"
	fmt.Println(permutation(s))
}

var result []string

func permutation(s string) []string {
	result = make([]string, 0)

	t := []byte(s)
	sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })

	backTrace(make([]byte, 0), t, make([]bool, len(s)))
	return result
}

func backTrace(path, sBytes []byte, used []bool) {
	if len(path) == len(sBytes) {
		result = append(result, string(path))
		return
	}
	for i := 0; i < len(sBytes); i++ {
		if used[i] {
			continue
		}
		if i-1 >= 0 && sBytes[i-1] == sBytes[i] && !used[i-1] {
			continue
		}
		used[i] = true
		path = append(path, sBytes[i])
		backTrace(path, sBytes, used)
		used[i] = false
		path = path[:len(path)-1]
	}
}
